<!DOCTYPE html>
<html lang="zh-CN">
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="robots" content="noodp" />
        <title>新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？ - L_B__</title><meta name="referrer" content="no-referrer">
<meta name="description" content="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？"><meta property="og:title" content="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？" />
<meta property="og:description" content="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" /><meta property="og:image" content="https://acking-you.github.io/logo.png"/><meta property="article:section" content="posts" />
<meta property="article:published_time" content="2022-02-16T00:00:00+00:00" />
<meta property="article:modified_time" content="2022-02-16T00:00:00+00:00" />

<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://acking-you.github.io/logo.png"/>

<meta name="twitter:title" content="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？"/>
<meta name="twitter:description" content="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？"/>
<meta name="application-name" content="FeelIt">
<meta name="apple-mobile-web-app-title" content="FeelIt"><meta name="theme-color" content="#ffffff"><meta name="msapplication-TileColor" content="#da532c"><link rel="canonical" href="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" /><link rel="prev" href="https://acking-you.github.io/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" /><link rel="next" href="https://acking-you.github.io/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" /><link rel="stylesheet" href="/css/page.min.css"><link rel="stylesheet" href="/css/home.min.css"><script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "新手用C++写了个泛型堆，效率竟比STL的更快？",
        "inLanguage": "zh-CN",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "https:\/\/acking-you.github.io\/posts\/%E6%96%B0%E6%89%8B%E7%94%A8c\u002b\u002b%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB\/"
        },"genre": "posts","keywords": "新手用C\u002b\u002b写了个泛型堆，效率竟比STL的更快？","wordcount":  3714 ,
        "url": "https:\/\/acking-you.github.io\/posts\/%E6%96%B0%E6%89%8B%E7%94%A8c\u002b\u002b%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB\/","datePublished": "2022-02-16T00:00:00+00:00","dateModified": "2022-02-16T00:00:00+00:00","publisher": {
            "@type": "Organization",
            "name": "作者"},"author": {
                "@type": "Person",
                "name": "作者"
            },"description": "新手用C++写了个泛型堆，效率竟比STL的更快？"
    }
    </script></head><body data-header-desktop="auto" data-header-mobile="auto"><script>(window.localStorage && localStorage.getItem('theme') ? localStorage.getItem('theme') === 'dark' : ('auto' === 'auto' ? window.matchMedia('(prefers-color-scheme: dark)').matches : 'auto' === 'dark')) && document.body.setAttribute('theme', 'dark');</script>

        <div id="mask"></div><div class="wrapper"><header class="desktop" id="header-desktop">
    <div class="header-wrapper">
        <div class="header-title">
            <a href="/" title="L_B__">L_B__</a>
        </div>
        <div class="menu">
            <div class="menu-inner"><a class="menu-item" href="/posts/"> 文章 </a><a class="menu-item" href="/tags/"> 标签 </a><a class="menu-item" href="/categories/"> 分类 </a><span class="menu-item delimiter"></span><span class="menu-item search" id="search-desktop">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-desktop">
                        <a href="#" class="search-button search-toggle" id="search-toggle-desktop" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-desktop" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-desktop">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </span><a href="javascript:void(0);" class="menu-item theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div>
        </div>
    </div>
</header><header class="mobile" id="header-mobile">
    <div class="header-container">
        <div class="header-wrapper">
            <div class="header-title">
                <a href="/" title="L_B__">L_B__</a>
            </div>
            <div class="menu-toggle" id="menu-toggle-mobile">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="menu" id="menu-mobile"><div class="search-wrapper">
                    <div class="search mobile" id="search-mobile">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-mobile">
                        <a href="#" class="search-button search-toggle" id="search-toggle-mobile" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-mobile" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-mobile">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </div>
                    <a href="#" class="search-cancel" id="search-cancel-mobile">
                        取消
                    </a>
                </div><a class="menu-item" href="/posts/" title="">文章</a><a class="menu-item" href="/tags/" title="">标签</a><a class="menu-item" href="/categories/" title="">分类</a><div class="menu-item"><a href="javascript:void(0);" class="theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div></div>
    </div>
</header><div class="search-dropdown desktop">
    <div id="search-dropdown-desktop"></div>
</div>
<div class="search-dropdown mobile">
    <div id="search-dropdown-mobile"></div>
</div><main class="main">
                <div class="container"><div class="toc" id="toc-auto">
            <h2 class="toc-title">目录</h2>
            <div class="toc-content" id="toc-content-auto"></div>
        </div><article class="page single" data-toc="disable"><div class="featured-image"><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/926beb3cfeb04153a3c69c11c604e8e9.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/926beb3cfeb04153a3c69c11c604e8e9.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/926beb3cfeb04153a3c69c11c604e8e9.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/926beb3cfeb04153a3c69c11c604e8e9.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/926beb3cfeb04153a3c69c11c604e8e9.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？" /></div><div class="single-card" data-image="true"><h2 class="single-title animated flipInX">新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？</h2><div class="post-meta">
                <div class="post-meta-line"><span class="post-author"><a href="/" title="Author" rel=" author" class="author"><i class="fas fa-user-circle fa-fw"></i>作者</a></span>&nbsp;<span class="post-category">出版于  <a href="/categories/%E6%89%8B%E5%86%99%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/"><i class="far fa-folder fa-fw"></i>手写数据结构</a></span></div>
                <div class="post-meta-line"><span><i class="far fa-calendar-alt fa-fw"></i>&nbsp;<time datetime="2022-02-16">2022-02-16</time></span>&nbsp;<span><i class="fas fa-pencil-alt fa-fw"></i>&nbsp;约 3714 字</span>&nbsp;
                    <span><i class="far fa-clock fa-fw"></i>&nbsp;预计阅读 8 分钟</span>&nbsp;</div>
            </div>
            
            <hr><div class="details toc" id="toc-static"  data-kept="">
                    <div class="details-summary toc-title">
                        <span>目录</span>
                        <span><i class="details-icon fas fa-angle-right"></i></span>
                    </div>
                    <div class="details-content toc-content" id="toc-content-static"><nav id="TableOfContents">
  <ul>
    <li><a href="#关于为什么突然想写一个模板类">关于为什么突然想写一个模板类？</a></li>
    <li><a href="#对刚用模板的c新手而言的几大坑点">对刚用模板的C++新手而言的几大坑点</a>
      <ul>
        <li><a href="#习惯性写h和cpp文件">习惯性写.h和.cpp文件</a></li>
        <li><a href="#对模板特化运用和理解很少">对模板特化运用和理解很少</a></li>
      </ul>
    </li>
    <li><a href="#我的heap实现">我的Heap实现</a>
      <ul>
        <li><a href="#总览heap类">总览Heap类</a></li>
        <li><a href="#关于堆化函数的实现">关于堆化函数的实现</a></li>
        <li><a href="#关于所用模板的说明">关于所用模板的说明</a></li>
        <li><a href="#整合所有代码实现heap类模板">整合所有代码，实现Heap类模板</a></li>
      </ul>
    </li>
    <li><a href="#我的heap测试">我的Heap测试</a>
      <ul>
        <li><a href="#正确性测试与stl-priority_queue对比">正确性测试(与STL priority_queue对比)</a></li>
        <li><a href="#效率测试与stl-priority_queue对比">效率测试(与STL priority_queue对比)</a></li>
        <li><a href="#解题实测leetcode-347-前-k-个高频元素">解题实测(LeetCode 347. 前 K 个高频元素)</a></li>
      </ul>
    </li>
    <li><a href="#总结">总结</a></li>
  </ul>
</nav></div>
                </div><div class="content" id="content"><h2 id="关于为什么突然想写一个模板类">关于为什么突然想写一个模板类？</h2>
<blockquote>
<p>嗯。。主要是因为最近在翻看《STL源码剖析》，然后发现原来STL源码是如此的庞大且复杂，而又及其具有条理，而其中最难的就是各个组件的关系，而对外所展现的效果就是泛型编程，对我这个初入门菜鸟来说的话，我之前对模板仅仅停留在知道，但没用过的阶段🤣</p>
</blockquote>
<p>由于STL库中对模板的骚操作一个接一个，没个模板的基础，根本就看不懂，所以我痛定思痛，一定要亲手用模板实现一个数据结构(之前用非模板实现过一些)。</p>
<p>好了，目标有了，用模板实现一个数据结构，那数据结构这么多，我到底实现哪个呢？要不就把堆给冲了？我一拍大腿，可行！👍</p>
<p>最后关于它的具体实现，我肯定不会像STL那样考虑的那么周到，组件分工齐全，毕竟STL是包含六大组件的！
具体如下图：
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/b2740fdd673e4eeaa45a2f81a181de71.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/b2740fdd673e4eeaa45a2f81a181de71.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/b2740fdd673e4eeaa45a2f81a181de71.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/b2740fdd673e4eeaa45a2f81a181de71.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/b2740fdd673e4eeaa45a2f81a181de71.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/b2740fdd673e4eeaa45a2f81a181de71.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<h2 id="对刚用模板的c新手而言的几大坑点">对刚用模板的C++新手而言的几大坑点</h2>
<h3 id="习惯性写h和cpp文件">习惯性写.h和.cpp文件</h3>
<blockquote>
<p>对于对C++有一定掌握，但基本没用过模板的人而言，声明与定义早就烂熟于心的.h和.cpp文件。</p>
</blockquote>
<ul>
<li>然而，当你使用模板的时候，再去吧声明和定义分开，将会产生一个错误！除非在.h文件末尾有包含.cpp文件。然而这样的操作是很多余的！</li>
</ul>
<p>所以在用模板实现类的时候，最好只写一个.h文件！</p>
<h3 id="对模板特化运用和理解很少">对模板特化运用和理解很少</h3>
<ul>
<li>我现在就处于这个状态，说不上来该怎么规范🤣</li>
</ul>
<h2 id="我的heap实现">我的Heap实现</h2>
<h3 id="总览heap类">总览Heap类</h3>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/5bcb7d4a50a94e07951442efb61952ec.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/5bcb7d4a50a94e07951442efb61952ec.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/5bcb7d4a50a94e07951442efb61952ec.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/5bcb7d4a50a94e07951442efb61952ec.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/5bcb7d4a50a94e07951442efb61952ec.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/5bcb7d4a50a94e07951442efb61952ec.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
<ul>
<li>这是我画的树状图，我设计的Heap一共分为以下三个部分：</li>
</ul>
<h4 id="一-成员变量">一、 成员变量</h4>
<p>这部分没啥好说的，就用一个 nums 指针存储变量数据，length 记录当前的 nums 已经使用的长度，capacity 存储当前 nums 的最大容量。</p>
<h4 id="二-静态成员函数">二、 静态成员函数</h4>
<p>我将堆的基本操作封装为静态成员变量的初衷是方便，对外实现堆化的功能，即使使用外部数组也能实现堆。
下面简单的介绍一下这几个函数（后面再详解）：</p>
<ol>
<li>sift_down()：接受四个参数，依次是用于向下堆化的数组，起始的堆化位置，结束的堆化位置，以及一个仿函数(用于设定最大/最小堆)。</li>
</ol>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="kt">void</span> <span class="nf">sift_down</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">start</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">len</span><span class="p">,</span> <span class="n">_CMP</span> <span class="n">cmp</span><span class="p">);</span>
</code></pre></div><ol start="2">
<li>sift_up()：向上堆化的操作，与上面的类似，少了结束信息，因为结束信息一般都是0.</li>
</ol>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">static</span> <span class="kt">void</span> <span class="nf">sift_up</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">start</span><span class="p">,</span> <span class="n">_CMP</span> <span class="n">cmp</span><span class="p">);</span>
</code></pre></div><ol start="3">
<li>heapify()：调用向下堆化函数，实现完全堆化，接收两个参数，待堆化数组和数组长度</li>
</ol>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"> <span class="k">static</span> <span class="kt">void</span> <span class="nf">heapify</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">len</span><span class="p">);</span>
</code></pre></div><ol start="4">
<li>print()：主要实现一个用于测试功能的泛型打印接口，接收的参数肯定就是数组和数组长度了。(略过，不重要)</li>
</ol>
<h4 id="三类的内部成员函数放源代码详解">三、类的内部成员函数(放源代码详解)</h4>
<ol>
<li>构造和析构函数：很简单的，我直接放源代码出来。</li>
</ol>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="n">Heap</span><span class="p">()</span> <span class="o">:</span> <span class="n">length</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span> <span class="n">capacity</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="p">{</span><span class="c1">//暂时没有对构造函数拓展的打算
</span><span class="c1"></span>     <span class="n">nums</span> <span class="o">=</span> <span class="k">new</span> <span class="n">_T</span><span class="p">[</span><span class="n">capacity</span><span class="p">];</span>
<span class="p">}</span>
<span class="o">~</span><span class="n">Heap</span><span class="p">(){</span>
     <span class="k">delete</span> <span class="p">[]</span><span class="n">nums</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><ol start="2">
<li>push()：每次入队后进行一次向上堆化，这个简单，直接调上面的静态接口就行了。<strong>注意：我这里采用的是倍增的方式进行延伸内存，一旦出现capacity不够用的情况，就重新分配内存，其中数据拷贝方面用了copy函数。</strong></li>
</ol>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="kt">void</span> <span class="nf">push</span><span class="p">(</span><span class="n">_T</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">length</span> <span class="o">&gt;=</span> <span class="n">capacity</span><span class="p">)</span> <span class="p">{</span><span class="c1">//两倍两倍的扩容
</span><span class="c1"></span>        <span class="n">_T</span> <span class="o">*</span><span class="n">t</span> <span class="o">=</span> <span class="n">nums</span><span class="p">;</span>
        <span class="n">capacity</span> <span class="o">*=</span> <span class="mi">2</span><span class="p">;</span>
        <span class="n">nums</span> <span class="o">=</span> <span class="k">new</span> <span class="n">_T</span><span class="p">[</span><span class="n">capacity</span><span class="p">];</span>
        <span class="n">std</span><span class="o">::</span><span class="n">copy</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">t</span> <span class="o">+</span> <span class="n">length</span><span class="p">,</span> <span class="n">nums</span><span class="p">);</span>
        <span class="k">delete</span><span class="p">[]</span> <span class="n">t</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="n">nums</span><span class="p">[</span><span class="n">length</span><span class="p">]</span> <span class="o">=</span> <span class="n">val</span><span class="p">;</span>
    <span class="n">sift_up</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">length</span><span class="p">,</span> <span class="n">_CMP</span><span class="p">());</span>
    <span class="n">length</span><span class="o">++</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><ol start="3">
<li>pop()：这个操作是需要一点技巧的&ndash;为了不破坏整体堆化的结构，我们<strong>直接把根部与尾部元素进行交换，再从根部往下重新堆化一次(注意此时堆化的终点应该要比原来小1)。</strong></li>
</ol>
<blockquote>
<p>还采取了C语言的断言方式，防止pop操作的时候，堆中已经没有元素。</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="kt">void</span> <span class="nf">pop</span><span class="p">()</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">length</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
        <span class="n">assert</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span>
    <span class="n">length</span><span class="o">--</span><span class="p">;</span>
    <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">length</span><span class="p">]);</span><span class="c1">//实际上pop操作就相当于堆排的一次过程
</span><span class="c1"></span>    <span class="n">sift_down</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">length</span><span class="p">,</span> <span class="n">_CMP</span><span class="p">());</span>
<span class="p">}</span>
</code></pre></div><ol start="4">
<li>top()：直接取根节点的值。</li>
</ol>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="n">_T</span> <span class="nf">top</span><span class="p">()</span> <span class="p">{</span>
    <span class="k">if</span> <span class="p">(</span><span class="n">length</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
        <span class="n">assert</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span>
    <span class="k">return</span> <span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
<span class="p">}</span>
</code></pre></div><ol start="5">
<li>print()：用于打印内部数据的接口。</li>
</ol>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="kt">void</span> <span class="nf">print</span><span class="p">()</span> <span class="p">{</span><span class="c1">//内部print方便测试
</span><span class="c1"></span>    <span class="n">print</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">length</span><span class="p">);</span><span class="c1">//调用静态print
</span><span class="c1"></span><span class="p">}</span>
</code></pre></div><h3 id="关于堆化函数的实现">关于堆化函数的实现</h3>
<ul>
<li>我直接开放代码实现，具体的理解靠大家了。</li>
</ul>
<p><strong>sift_down()</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
<span class="k">static</span> <span class="kt">void</span> <span class="n">sift_down</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">start</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">len</span><span class="p">,</span> <span class="n">_CMP</span> <span class="n">cmp</span><span class="p">)</span> <span class="p">{</span><span class="c1">//最小堆还是最大堆由cmp决定
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">end</span> <span class="o">=</span> <span class="n">len</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">parent</span> <span class="o">=</span> <span class="n">start</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">child</span> <span class="o">&lt;</span> <span class="n">end</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">child</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">&lt;</span> <span class="n">end</span> <span class="o">&amp;&amp;</span> <span class="n">cmp</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]))</span>
            <span class="n">child</span><span class="o">++</span><span class="p">;</span>
        <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">cmp</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]))</span> <span class="p">{</span>
            <span class="k">break</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
            <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]);</span>
            <span class="n">parent</span> <span class="o">=</span> <span class="n">child</span><span class="p">;</span>
            <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><p><strong>sift_up</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
<span class="k">static</span> <span class="kt">void</span> <span class="n">sift_up</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">start</span><span class="p">,</span> <span class="n">_CMP</span> <span class="n">cmp</span><span class="p">)</span> <span class="p">{</span><span class="c1">//最小堆还是最大堆由cmp决定
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">end</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">child</span> <span class="o">=</span> <span class="n">start</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">parent</span> <span class="o">=</span> <span class="p">(</span><span class="n">child</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">child</span> <span class="o">&gt;</span> <span class="n">end</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">cmp</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]))</span> <span class="p">{</span>
            <span class="k">break</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
            <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]);</span>
            <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span><span class="p">;</span>
            <span class="n">parent</span> <span class="o">=</span> <span class="p">(</span><span class="n">child</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><p><strong>heapify()</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
<span class="k">static</span> <span class="kt">void</span> <span class="n">heapify</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">len</span><span class="p">)</span> <span class="p">{</span><span class="c1">//用于对数组进行堆化
</span><span class="c1"></span>    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">len</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">sift_down</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">len</span><span class="p">,</span> <span class="n">_CMP</span><span class="p">());</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><p><strong>print()</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
<span class="k">static</span> <span class="kt">void</span> <span class="n">print</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">length</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">length</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="n">std</span><span class="o">::</span><span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;&lt;</span> <span class="sc">&#39; &#39;</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><h3 id="关于所用模板的说明">关于所用模板的说明</h3>
<p><strong>类模板(全局均可用的类型参数)</strong>：</p>
<blockquote>
<p>其中 _T 用于表示数组元素的类型，默认为int，_CMP 则是一个类(仿函数)的类型，<strong>默认为已经提供的cmp仿函数，所以如果为自定义类型构建堆，则一定要自己写好相应的仿函数进行传递。</strong></p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span> <span class="o">=</span> <span class="kt">int</span><span class="o">&gt;</span> <span class="c1">//用于默认排序的仿函数，默认为大顶堆
</span><span class="c1"></span><span class="k">class</span> <span class="nc">cmp</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">bool</span> <span class="k">operator</span><span class="p">()(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="n">T</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">a</span> <span class="o">&lt;</span> <span class="n">b</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">_T</span> <span class="o">=</span> <span class="kt">int</span><span class="p">,</span> <span class="k">typename</span> <span class="n">_CMP</span> <span class="o">=</span> <span class="n">cmp</span><span class="o">&lt;</span><span class="n">_T</span><span class="o">&gt;&gt;</span>
</code></pre></div><p><strong>成员函数模板</strong></p>
<blockquote>
<p>为了<strong>便于外界使用静态成员函数进行相应的操作，所以每个静态成员函数都提供了对应的类型模板</strong>，但比较操作的仿函数用的还是和类模板一样的类型。</p>
</blockquote>
<p>如：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
<span class="k">static</span> <span class="kt">void</span> <span class="n">sift_up</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">start</span><span class="p">,</span> <span class="n">_CMP</span> <span class="n">cmp</span><span class="p">)</span> <span class="p">{</span><span class="c1">//最小堆还是最大堆由cmp决定
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">end</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">child</span> <span class="o">=</span> <span class="n">start</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">parent</span> <span class="o">=</span> <span class="p">(</span><span class="n">child</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>
    <span class="k">while</span> <span class="p">(</span><span class="n">child</span> <span class="o">&gt;</span> <span class="n">end</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">cmp</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]))</span> <span class="p">{</span>
            <span class="k">break</span><span class="p">;</span>
        <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
            <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]);</span>
            <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span><span class="p">;</span>
            <span class="n">parent</span> <span class="o">=</span> <span class="p">(</span><span class="n">child</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><h3 id="整合所有代码实现heap类模板">整合所有代码，实现Heap类模板</h3>
<blockquote>
<p>这里用一个命名空间套住是最好，防止命名冲突！我这里用的自己常用的网名hhh</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="c1">//
</span><span class="c1">// Created by Alone on 2021/10/2.
</span><span class="c1">//
</span><span class="c1"></span>
<span class="cp">#ifndef MY_TINY_STL_HEAP_H
</span><span class="cp">#define MY_TINY_STL_HEAP_H
</span><span class="cp"></span>
<span class="cp">#include</span> <span class="cpf">&lt;iostream&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;cassert&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;algorithm&gt;</span><span class="cp">
</span><span class="cp"></span>
<span class="k">namespace</span> <span class="n">L_B__</span> <span class="p">{</span>
    <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">=</span><span class="kt">int</span><span class="o">&gt;</span><span class="c1">//用于默认排序的仿函数，默认为大顶堆
</span><span class="c1"></span>    <span class="k">class</span> <span class="nc">cmp</span> <span class="p">{</span>
    <span class="k">public</span><span class="o">:</span>
        <span class="kt">bool</span> <span class="k">operator</span><span class="p">()(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="n">T</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">return</span> <span class="n">a</span> <span class="o">&lt;</span> <span class="n">b</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">};</span>

<span class="c1">//@模板类的实现
</span><span class="c1"></span>    <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">_T</span><span class="o">=</span><span class="kt">int</span><span class="p">,</span> <span class="k">typename</span> <span class="n">_CMP</span> <span class="o">=</span> <span class="n">cmp</span><span class="o">&lt;</span><span class="n">_T</span><span class="o">&gt;&gt;</span>
    <span class="k">class</span> <span class="nc">Heap</span> <span class="p">{</span>
        <span class="c1">//私有成员
</span><span class="c1"></span>        <span class="n">_T</span> <span class="o">*</span><span class="n">nums</span><span class="p">;</span>
        <span class="n">size_t</span> <span class="n">length</span><span class="p">;</span>
        <span class="n">size_t</span> <span class="n">capacity</span><span class="p">;</span>
    <span class="k">public</span><span class="o">:</span><span class="c1">//@静态成员函数，对外对内都能实现功能
</span><span class="c1"></span>        <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
        <span class="k">static</span> <span class="kt">void</span> <span class="n">sift_down</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">start</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">len</span><span class="p">,</span> <span class="n">_CMP</span> <span class="n">cmp</span><span class="p">)</span> <span class="p">{</span><span class="c1">//最小堆还是最大堆由cmp决定
</span><span class="c1"></span>            <span class="kt">int</span> <span class="n">end</span> <span class="o">=</span> <span class="n">len</span><span class="p">;</span>
            <span class="kt">int</span> <span class="n">parent</span> <span class="o">=</span> <span class="n">start</span><span class="p">;</span>
            <span class="kt">int</span> <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">child</span> <span class="o">&lt;</span> <span class="n">end</span><span class="p">)</span> <span class="p">{</span>
                <span class="k">if</span> <span class="p">(</span><span class="n">child</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">&lt;</span> <span class="n">end</span> <span class="o">&amp;&amp;</span> <span class="n">cmp</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]))</span>
                    <span class="n">child</span><span class="o">++</span><span class="p">;</span>
                <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">cmp</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]))</span> <span class="p">{</span>
                    <span class="k">break</span><span class="p">;</span>
                <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
                    <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]);</span>
                    <span class="n">parent</span> <span class="o">=</span> <span class="n">child</span><span class="p">;</span>
                    <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
                <span class="p">}</span>
            <span class="p">}</span>
        <span class="p">}</span>

        <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
        <span class="k">static</span> <span class="kt">void</span> <span class="n">sift_up</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">start</span><span class="p">,</span> <span class="n">_CMP</span> <span class="n">cmp</span><span class="p">)</span> <span class="p">{</span><span class="c1">//最小堆还是最大堆由cmp决定
</span><span class="c1"></span>            <span class="kt">int</span> <span class="n">end</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
            <span class="kt">int</span> <span class="n">child</span> <span class="o">=</span> <span class="n">start</span><span class="p">;</span>
            <span class="kt">int</span> <span class="n">parent</span> <span class="o">=</span> <span class="p">(</span><span class="n">child</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">child</span> <span class="o">&gt;</span> <span class="n">end</span><span class="p">)</span> <span class="p">{</span>
                <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">cmp</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]))</span> <span class="p">{</span>
                    <span class="k">break</span><span class="p">;</span>
                <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
                    <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]);</span>
                    <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span><span class="p">;</span>
                    <span class="n">parent</span> <span class="o">=</span> <span class="p">(</span><span class="n">child</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>
                <span class="p">}</span>
            <span class="p">}</span>
        <span class="p">}</span>

        <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
        <span class="k">static</span> <span class="kt">void</span> <span class="n">heapify</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">len</span><span class="p">)</span> <span class="p">{</span><span class="c1">//用于对数组进行堆化
</span><span class="c1"></span>            <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">len</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">sift_down</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">len</span><span class="p">,</span> <span class="n">_CMP</span><span class="p">());</span>
            <span class="p">}</span>
        <span class="p">}</span>

        <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
        <span class="k">static</span> <span class="kt">void</span> <span class="n">print</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">length</span><span class="p">)</span> <span class="p">{</span><span class="c1">//专为打印原始数组
</span><span class="c1"></span>            <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">length</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">std</span><span class="o">::</span><span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;&lt;</span> <span class="sc">&#39; &#39;</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>

    <span class="k">public</span><span class="o">:</span><span class="c1">//@基本的内部成员函数
</span><span class="c1"></span>        <span class="n">Heap</span><span class="p">()</span> <span class="o">:</span> <span class="n">length</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span> <span class="n">capacity</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="p">{</span><span class="c1">//暂时没有对构造函数拓展的打算
</span><span class="c1"></span>            <span class="n">nums</span> <span class="o">=</span> <span class="k">new</span> <span class="n">_T</span><span class="p">[</span><span class="n">capacity</span><span class="p">];</span>
        <span class="p">}</span>

        <span class="o">~</span><span class="n">Heap</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">delete</span><span class="p">[]</span><span class="n">nums</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="kt">void</span> <span class="nf">push</span><span class="p">(</span><span class="n">_T</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">length</span> <span class="o">&gt;=</span> <span class="n">capacity</span><span class="p">)</span> <span class="p">{</span><span class="c1">//两倍两倍的扩容
</span><span class="c1"></span>                <span class="n">_T</span> <span class="o">*</span><span class="n">t</span> <span class="o">=</span> <span class="n">nums</span><span class="p">;</span>
                <span class="n">capacity</span> <span class="o">*=</span> <span class="mi">2</span><span class="p">;</span>
                <span class="n">nums</span> <span class="o">=</span> <span class="k">new</span> <span class="n">_T</span><span class="p">[</span><span class="n">capacity</span><span class="p">];</span>
                <span class="n">std</span><span class="o">::</span><span class="n">copy</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">t</span> <span class="o">+</span> <span class="n">length</span><span class="p">,</span> <span class="n">nums</span><span class="p">);</span>
                <span class="k">delete</span><span class="p">[]</span> <span class="n">t</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="n">nums</span><span class="p">[</span><span class="n">length</span><span class="p">]</span> <span class="o">=</span> <span class="n">val</span><span class="p">;</span>
            <span class="n">sift_up</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">length</span><span class="p">,</span> <span class="n">_CMP</span><span class="p">());</span>
            <span class="n">length</span><span class="o">++</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="kt">void</span> <span class="nf">pop</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">length</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
                <span class="n">assert</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span>
            <span class="n">length</span><span class="o">--</span><span class="p">;</span>
            <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">length</span><span class="p">]);</span><span class="c1">//实际上pop操作就相当于堆排的一次过程
</span><span class="c1"></span>            <span class="n">sift_down</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">length</span><span class="p">,</span> <span class="n">_CMP</span><span class="p">());</span>
        <span class="p">}</span>

        <span class="n">_T</span> <span class="nf">top</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">length</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
                <span class="n">assert</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span>
            <span class="k">return</span> <span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
        <span class="p">}</span>

        <span class="kt">void</span> <span class="nf">print</span><span class="p">()</span> <span class="p">{</span><span class="c1">//内部print方便测试
</span><span class="c1"></span>            <span class="n">print</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">length</span><span class="p">);</span>
        <span class="p">}</span>
    <span class="p">};</span>
<span class="p">}</span>

<span class="cp">#endif </span><span class="c1">//MY_TINY_STL_HEAP_H
</span></code></pre></div><h2 id="我的heap测试">我的Heap测试</h2>
<h3 id="正确性测试与stl-priority_queue对比">正确性测试(与STL priority_queue对比)</h3>
<blockquote>
<p>经历这数千万数据的测试，仍然和STL的正确性是一样的，说明正确性是有了保障的。
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/1fdf2c1cde6d467997ddb2d9125d29c6.png"
        data-srcset="https://img-blog.csdnimg.cn/1fdf2c1cde6d467997ddb2d9125d29c6.png, https://img-blog.csdnimg.cn/1fdf2c1cde6d467997ddb2d9125d29c6.png 1.5x, https://img-blog.csdnimg.cn/1fdf2c1cde6d467997ddb2d9125d29c6.png 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/1fdf2c1cde6d467997ddb2d9125d29c6.png"
        title="https://img-blog.csdnimg.cn/1fdf2c1cde6d467997ddb2d9125d29c6.png" /></p>
</blockquote>
<p><strong>测试代码</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cp">#include</span> <span class="cpf">&#34;Heap.h&#34;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;ctime&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;queue&gt;</span><span class="cp">
</span><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="cp">#define MAX_SIZE 10000000
</span><span class="cp"></span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
    <span class="n">L_B__</span><span class="o">::</span><span class="n">Heap</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">a</span><span class="p">;</span>
    <span class="n">priority_queue</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">Q</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">step</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">MAX_SIZE</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="n">a</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">step</span><span class="o">%</span><span class="n">i</span><span class="p">);</span>
        <span class="n">Q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">step</span><span class="o">%</span><span class="n">i</span><span class="p">);</span>
        <span class="n">step</span> <span class="o">+=</span> <span class="mi">2</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;STL-&gt;&#34;</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">10</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">auto</span> <span class="n">t</span> <span class="o">=</span> <span class="n">move</span><span class="p">(</span><span class="n">Q</span><span class="p">.</span><span class="n">top</span><span class="p">());</span>
        <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">t</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="p">;</span>
        <span class="n">Q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
    <span class="p">}</span>
    <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">endl</span><span class="p">;</span>
    <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">&#34;My-&gt;&#34;</span><span class="p">;</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="mi">10</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">auto</span> <span class="n">t</span> <span class="o">=</span> <span class="n">move</span><span class="p">(</span><span class="n">a</span><span class="p">.</span><span class="n">top</span><span class="p">());</span>
        <span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">t</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="p">;</span>
        <span class="n">a</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><h3 id="效率测试与stl-priority_queue对比">效率测试(与STL priority_queue对比)</h3>
<p><strong>1000w数据两者的push和pop速度对比</strong>
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/e4c3cd9b40294b2884fb370f656ef72b.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_16,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/e4c3cd9b40294b2884fb370f656ef72b.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_16%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/e4c3cd9b40294b2884fb370f656ef72b.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_16%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/e4c3cd9b40294b2884fb370f656ef72b.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_16%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/e4c3cd9b40294b2884fb370f656ef72b.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_16,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/e4c3cd9b40294b2884fb370f656ef72b.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_16,color_FFFFFF,t_70,g_se,x_16" />
欧耶！比STL快两倍！！🐱‍🏍</p>
<blockquote>
<p>其实这样不是很奇怪，STL本来就要实现和考虑很多事情，各种组件的套娃，而我们只是实现了这样一个简单的堆，那当然快很多了。</p>
</blockquote>
<p><strong>测试源代码</strong></p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cp">#include</span> <span class="cpf">&#34;Heap.h&#34;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;ctime&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;queue&gt;</span><span class="cp">
</span><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="cp">#define MAX_SIZE 10000000
</span><span class="cp"></span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
    <span class="n">L_B__</span><span class="o">::</span><span class="n">Heap</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">a</span><span class="p">;</span>
    <span class="n">priority_queue</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">Q</span><span class="p">;</span>
    <span class="k">auto</span> <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="c1">//@push测试
</span><span class="c1"></span>    <span class="kt">int</span> <span class="n">step</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">MAX_SIZE</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="n">Q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">step</span><span class="o">%</span><span class="n">i</span><span class="p">);</span>
        <span class="n">step</span> <span class="o">+=</span> <span class="mi">2</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;STL Push:&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="n">endl</span><span class="p">;</span>
    <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="n">step</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">MAX_SIZE</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="n">a</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">step</span><span class="o">%</span><span class="n">i</span><span class="p">);</span>
        <span class="n">step</span> <span class="o">+=</span> <span class="mi">2</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;My Push:&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="n">endl</span><span class="p">;</span>

    <span class="c1">//@pop测试
</span><span class="c1"></span>    <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">MAX_SIZE</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="n">Q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
    <span class="p">}</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;STL Pop:&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="n">endl</span><span class="p">;</span>
    <span class="n">start</span> <span class="o">=</span> <span class="n">clock</span><span class="p">();</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">MAX_SIZE</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="n">a</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
    <span class="p">}</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="s">&#34;My Pop:&#34;</span><span class="o">&lt;&lt;</span><span class="n">clock</span><span class="p">()</span><span class="o">-</span><span class="n">start</span><span class="o">&lt;&lt;</span><span class="s">&#34;ms&#34;</span><span class="o">&lt;&lt;</span><span class="n">endl</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div><h3 id="解题实测leetcode-347-前-k-个高频元素">解题实测(LeetCode 347. 前 K 个高频元素)</h3>
<blockquote>
<p>我去，果然比stl的快不少🤣
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/97db844068014f418adb660ac69e1a79.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        data-srcset="https://img-blog.csdnimg.cn/97db844068014f418adb660ac69e1a79.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16, https://img-blog.csdnimg.cn/97db844068014f418adb660ac69e1a79.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 1.5x, https://img-blog.csdnimg.cn/97db844068014f418adb660ac69e1a79.png?x-oss-process=image/watermark%2ctype_ZHJvaWRzYW5zZmFsbGJhY2s%2cshadow_50%2ctext_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=%2csize_20%2ccolor_FFFFFF%2ct_70%2cg_se%2cx_16 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/97db844068014f418adb660ac69e1a79.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"
        title="https://img-blog.csdnimg.cn/97db844068014f418adb660ac69e1a79.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16" /></p>
</blockquote>
<blockquote>
<p>直接把代码cv放到LC前面，然后测试使用自定义类型的情况。
<strong>解题代码</strong>：</p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">struct</span> <span class="nc">S</span><span class="p">{</span>
    <span class="kt">int</span> <span class="n">a</span><span class="p">,</span><span class="n">b</span><span class="p">;</span>
<span class="p">};</span>
<span class="k">class</span> <span class="nc">cmp</span><span class="p">{</span>
    <span class="k">public</span><span class="o">:</span>
    <span class="kt">bool</span> <span class="k">operator</span><span class="p">()(</span><span class="n">S</span><span class="o">&amp;</span><span class="n">a</span><span class="p">,</span><span class="n">S</span><span class="o">&amp;</span><span class="n">b</span><span class="p">){</span>
        <span class="k">return</span> <span class="n">a</span><span class="p">.</span><span class="n">b</span><span class="o">&lt;</span><span class="n">b</span><span class="p">.</span><span class="n">b</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="k">namespace</span> <span class="n">L_B__</span> <span class="p">{</span>
    <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">=</span><span class="kt">int</span><span class="o">&gt;</span><span class="c1">//用于默认排序的仿函数，默认为大顶堆
</span><span class="c1"></span>    <span class="k">class</span> <span class="nc">cmp</span> <span class="p">{</span>
    <span class="k">public</span><span class="o">:</span>
        <span class="kt">bool</span> <span class="k">operator</span><span class="p">()(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">a</span><span class="p">,</span> <span class="n">T</span> <span class="o">&amp;</span><span class="n">b</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">return</span> <span class="n">a</span> <span class="o">&lt;</span> <span class="n">b</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">};</span>

<span class="c1">//@模板类的实现
</span><span class="c1"></span>    <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">_T</span><span class="o">=</span><span class="kt">int</span><span class="p">,</span> <span class="k">typename</span> <span class="n">_CMP</span> <span class="o">=</span> <span class="n">cmp</span><span class="o">&lt;</span><span class="n">_T</span><span class="o">&gt;&gt;</span>
    <span class="k">class</span> <span class="nc">Heap</span> <span class="p">{</span>
        <span class="c1">//私有成员
</span><span class="c1"></span>        <span class="n">_T</span> <span class="o">*</span><span class="n">nums</span><span class="p">;</span>
        <span class="n">size_t</span> <span class="n">length</span><span class="p">;</span>
        <span class="n">size_t</span> <span class="n">capacity</span><span class="p">;</span>
    <span class="k">public</span><span class="o">:</span><span class="c1">//@静态成员函数，对外对内都能实现功能
</span><span class="c1"></span>        <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
        <span class="k">static</span> <span class="kt">void</span> <span class="n">sift_down</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">start</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">len</span><span class="p">,</span> <span class="n">_CMP</span> <span class="n">cmp</span><span class="p">)</span> <span class="p">{</span><span class="c1">//最小堆还是最大堆由cmp决定
</span><span class="c1"></span>            <span class="kt">int</span> <span class="n">end</span> <span class="o">=</span> <span class="n">len</span><span class="p">;</span>
            <span class="kt">int</span> <span class="n">parent</span> <span class="o">=</span> <span class="n">start</span><span class="p">;</span>
            <span class="kt">int</span> <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">child</span> <span class="o">&lt;</span> <span class="n">end</span><span class="p">)</span> <span class="p">{</span>
                <span class="k">if</span> <span class="p">(</span><span class="n">child</span> <span class="o">+</span> <span class="mi">1</span> <span class="o">&lt;</span> <span class="n">end</span> <span class="o">&amp;&amp;</span> <span class="n">cmp</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]))</span>
                    <span class="n">child</span><span class="o">++</span><span class="p">;</span>
                <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">cmp</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]))</span> <span class="p">{</span>
                    <span class="k">break</span><span class="p">;</span>
                <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
                    <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]);</span>
                    <span class="n">parent</span> <span class="o">=</span> <span class="n">child</span><span class="p">;</span>
                    <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span> <span class="o">*</span> <span class="mi">2</span> <span class="o">+</span> <span class="mi">1</span><span class="p">;</span>
                <span class="p">}</span>
            <span class="p">}</span>
        <span class="p">}</span>

        <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
        <span class="k">static</span> <span class="kt">void</span> <span class="n">sift_up</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">start</span><span class="p">,</span> <span class="n">_CMP</span> <span class="n">cmp</span><span class="p">)</span> <span class="p">{</span><span class="c1">//最小堆还是最大堆由cmp决定
</span><span class="c1"></span>            <span class="kt">int</span> <span class="n">end</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span>
            <span class="kt">int</span> <span class="n">child</span> <span class="o">=</span> <span class="n">start</span><span class="p">;</span>
            <span class="kt">int</span> <span class="n">parent</span> <span class="o">=</span> <span class="p">(</span><span class="n">child</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>
            <span class="k">while</span> <span class="p">(</span><span class="n">child</span> <span class="o">&gt;</span> <span class="n">end</span><span class="p">)</span> <span class="p">{</span>
                <span class="k">if</span> <span class="p">(</span><span class="o">!</span><span class="n">cmp</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]))</span> <span class="p">{</span>
                    <span class="k">break</span><span class="p">;</span>
                <span class="p">}</span> <span class="k">else</span> <span class="p">{</span>
                    <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="n">parent</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">child</span><span class="p">]);</span>
                    <span class="n">child</span> <span class="o">=</span> <span class="n">parent</span><span class="p">;</span>
                    <span class="n">parent</span> <span class="o">=</span> <span class="p">(</span><span class="n">child</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span><span class="p">;</span>
                <span class="p">}</span>
            <span class="p">}</span>
        <span class="p">}</span>

        <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
        <span class="k">static</span> <span class="kt">void</span> <span class="n">heapify</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">len</span><span class="p">)</span> <span class="p">{</span><span class="c1">//用于对数组进行堆化
</span><span class="c1"></span>            <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">len</span> <span class="o">-</span> <span class="mi">1</span><span class="p">;</span> <span class="n">i</span> <span class="o">&gt;=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span><span class="o">--</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">sift_down</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">i</span><span class="p">,</span> <span class="n">len</span><span class="p">,</span> <span class="n">_CMP</span><span class="p">());</span>
            <span class="p">}</span>
        <span class="p">}</span>

        <span class="k">template</span><span class="o">&lt;</span><span class="k">typename</span> <span class="n">T</span><span class="o">&gt;</span>
        <span class="k">static</span> <span class="kt">void</span> <span class="n">print</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">nums</span><span class="p">,</span> <span class="n">size_t</span> <span class="n">length</span><span class="p">)</span> <span class="p">{</span><span class="c1">//专为打印原始数组
</span><span class="c1"></span>            <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">length</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="p">{</span>
                <span class="n">std</span><span class="o">::</span><span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="n">nums</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;&lt;</span> <span class="sc">&#39; &#39;</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>

    <span class="k">public</span><span class="o">:</span><span class="c1">//@基本的内部成员函数
</span><span class="c1"></span>        <span class="n">Heap</span><span class="p">()</span> <span class="o">:</span> <span class="n">length</span><span class="p">(</span><span class="mi">0</span><span class="p">),</span> <span class="n">capacity</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="p">{</span><span class="c1">//暂时没有对构造函数拓展的打算
</span><span class="c1"></span>            <span class="n">nums</span> <span class="o">=</span> <span class="k">new</span> <span class="n">_T</span><span class="p">[</span><span class="n">capacity</span><span class="p">];</span>
        <span class="p">}</span>

        <span class="o">~</span><span class="n">Heap</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">delete</span><span class="p">[]</span><span class="n">nums</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="kt">void</span> <span class="nf">push</span><span class="p">(</span><span class="n">_T</span> <span class="n">val</span><span class="p">)</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">length</span> <span class="o">&gt;=</span> <span class="n">capacity</span><span class="p">)</span> <span class="p">{</span><span class="c1">//两倍两倍的扩容
</span><span class="c1"></span>                <span class="n">_T</span> <span class="o">*</span><span class="n">t</span> <span class="o">=</span> <span class="n">nums</span><span class="p">;</span>
                <span class="n">capacity</span> <span class="o">*=</span> <span class="mi">2</span><span class="p">;</span>
                <span class="n">nums</span> <span class="o">=</span> <span class="k">new</span> <span class="n">_T</span><span class="p">[</span><span class="n">capacity</span><span class="p">];</span>
                <span class="n">std</span><span class="o">::</span><span class="n">copy</span><span class="p">(</span><span class="n">t</span><span class="p">,</span> <span class="n">t</span> <span class="o">+</span> <span class="n">length</span><span class="p">,</span> <span class="n">nums</span><span class="p">);</span>
                <span class="k">delete</span><span class="p">[]</span> <span class="n">t</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="n">nums</span><span class="p">[</span><span class="n">length</span><span class="p">]</span> <span class="o">=</span> <span class="n">val</span><span class="p">;</span>
            <span class="n">sift_up</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">length</span><span class="p">,</span> <span class="n">_CMP</span><span class="p">());</span>
            <span class="n">length</span><span class="o">++</span><span class="p">;</span>
        <span class="p">}</span>

        <span class="kt">void</span> <span class="nf">pop</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">length</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
                <span class="n">assert</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span>
            <span class="n">length</span><span class="o">--</span><span class="p">;</span>
            <span class="n">std</span><span class="o">::</span><span class="n">swap</span><span class="p">(</span><span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">],</span> <span class="n">nums</span><span class="p">[</span><span class="n">length</span><span class="p">]);</span><span class="c1">//实际上pop操作就相当于堆排的一次过程
</span><span class="c1"></span>            <span class="n">sift_down</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="n">length</span><span class="p">,</span> <span class="n">_CMP</span><span class="p">());</span>
        <span class="p">}</span>

        <span class="n">_T</span> <span class="nf">top</span><span class="p">()</span> <span class="p">{</span>
            <span class="k">if</span> <span class="p">(</span><span class="n">length</span> <span class="o">==</span> <span class="mi">0</span><span class="p">)</span>
                <span class="n">assert</span><span class="p">(</span><span class="mi">0</span><span class="p">);</span>
            <span class="k">return</span> <span class="n">nums</span><span class="p">[</span><span class="mi">0</span><span class="p">];</span>
        <span class="p">}</span>

        <span class="kt">void</span> <span class="nf">print</span><span class="p">()</span> <span class="p">{</span><span class="c1">//内部print方便测试
</span><span class="c1"></span>            <span class="n">print</span><span class="p">(</span><span class="n">nums</span><span class="p">,</span> <span class="n">length</span><span class="p">);</span>
        <span class="p">}</span>
    <span class="p">};</span>
<span class="p">}</span>



<span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span> <span class="n">topKFrequent</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&amp;</span> <span class="n">nums</span><span class="p">,</span> <span class="kt">int</span> <span class="n">k</span><span class="p">)</span> <span class="p">{</span>
            <span class="n">unordered_map</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span><span class="kt">int</span><span class="o">&gt;</span><span class="n">t</span><span class="p">;</span>
            <span class="c1">//开始映射hashmap
</span><span class="c1"></span>            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="nl">s</span><span class="p">:</span><span class="n">nums</span><span class="p">){</span>
                <span class="n">t</span><span class="p">[</span><span class="n">s</span><span class="p">]</span><span class="o">++</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="n">L_B__</span><span class="o">::</span><span class="n">Heap</span><span class="o">&lt;</span><span class="n">S</span><span class="p">,</span><span class="n">cmp</span><span class="o">&gt;</span><span class="n">Q</span><span class="p">;</span>
            <span class="k">for</span><span class="p">(</span><span class="n">unordered_map</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span><span class="kt">int</span><span class="o">&gt;::</span><span class="n">iterator</span> <span class="n">it</span><span class="o">=</span><span class="n">t</span><span class="p">.</span><span class="n">begin</span><span class="p">();</span><span class="n">it</span><span class="o">!=</span><span class="n">t</span><span class="p">.</span><span class="n">end</span><span class="p">();</span><span class="n">it</span><span class="o">++</span><span class="p">){</span>
                <span class="n">Q</span><span class="p">.</span><span class="n">push</span><span class="p">({</span><span class="n">it</span><span class="o">-&gt;</span><span class="n">first</span><span class="p">,</span><span class="n">it</span><span class="o">-&gt;</span><span class="n">second</span><span class="p">});</span>
            <span class="p">}</span>
            <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="n">res</span><span class="p">;</span>
            <span class="c1">//得到前k个最大的元素
</span><span class="c1"></span>            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">k</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
                <span class="k">auto</span> <span class="n">t</span> <span class="o">=</span> <span class="n">Q</span><span class="p">.</span><span class="n">top</span><span class="p">();</span><span class="n">Q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span>
                <span class="n">res</span><span class="p">.</span><span class="n">push_back</span><span class="p">(</span><span class="n">t</span><span class="p">.</span><span class="n">a</span><span class="p">);</span>
            <span class="p">}</span>
        <span class="k">return</span> <span class="n">res</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></div><h2 id="总结">总结</h2>
<p>对于模板的运用，现在才刚开始入门(入门都不到&hellip;)，给我的感觉是STL源码的包袱很重，各个组件高度关联，所以能够通过一个容器实现的算法有很多很多！我这个新手还不配高攀，只能仰望了，当然平时随便写写乐色代码也是可以滴，至少可以吹牛说比STL还快了🤣</p>
</div><div class="post-footer" id="post-footer">
    <div class="post-info"><div class="post-info-tag"><span><a href="/tags/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/">新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？</a>
                </span></div><div class="post-info-line"><div class="post-info-mod">
                <span>更新于 2022-02-16</span>
            </div><div class="post-info-mod"></div>
        </div><div class="post-info-share">
            <span><a href="javascript:void(0);" title="分享到 Twitter" data-sharer="twitter" data-url="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" data-title="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？" data-hashtags="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？"><i class="fab fa-twitter fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Facebook" data-sharer="facebook" data-url="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" data-hashtag="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？"><i class="fab fa-facebook-square fa-fw"></i></a><a href="javascript:void(0);" title="分享到 WhatsApp" data-sharer="whatsapp" data-url="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" data-title="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？" data-web><i class="fab fa-whatsapp fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Line" data-sharer="line" data-url="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" data-title="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？"><i class="fab fa-line fa-fw"></i></a><a href="javascript:void(0);" title="分享到 微博" data-sharer="weibo" data-url="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" data-title="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？" data-image="https://img-blog.csdnimg.cn/926beb3cfeb04153a3c69c11c604e8e9.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAQ19ZQ0JYIFB5X1lZRFM=,size_20,color_FFFFFF,t_70,g_se,x_16"><i class="fab fa-weibo fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Myspace" data-sharer="myspace" data-url="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" data-title="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？" data-description="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？"><i data-svg-src="/lib/simple-icons/icons/myspace.min.svg"></i></a><a href="javascript:void(0);" title="分享到 Blogger" data-sharer="blogger" data-url="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" data-title="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？" data-description="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？"><i class="fab fa-blogger fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Evernote" data-sharer="evernote" data-url="https://acking-you.github.io/posts/%E6%96%B0%E6%89%8B%E7%94%A8c&#43;&#43;%E5%86%99%E4%BA%86%E4%B8%AA%E6%B3%9B%E5%9E%8B%E5%A0%86%E6%95%88%E7%8E%87%E7%AB%9F%E6%AF%94stl%E7%9A%84%E6%9B%B4%E5%BF%AB/" data-title="新手用C&#43;&#43;写了个泛型堆，效率竟比STL的更快？"><i class="fab fa-evernote fa-fw"></i></a></span>
        </div></div><div class="post-nav"><a href="/posts/%E6%9D%A5%E8%87%AA%E4%B8%8A%E5%B8%9D%E7%9A%84%E9%AA%B0%E5%AD%90-treap%E6%A0%91%E5%A0%86%E8%AF%A6%E8%A7%A3/" class="prev" rel="prev" title="来自上帝的骰子---Treap(树堆)详解"><i class="fas fa-angle-left fa-fw"></i>Previous Post</a>
            <a href="/posts/%E5%BE%92%E6%89%8B%E5%86%99%E7%9A%84avl%E7%AB%9F%E7%84%B6%E6%AF%94stl%E4%B8%AD%E7%9A%84%E7%BA%A2%E9%BB%91%E6%A0%91%E6%95%88%E7%8E%87%E6%9B%B4%E9%AB%98/" class="next" rel="next" title="徒手写的AVL竟然比STL中的红黑树效率更高？✨">Next Post<i class="fas fa-angle-right fa-fw"></i></a></div></div>
</div></article></div>
            </main>
            <footer class="footer"><div class="footer-container"><div class="footer-line">由 <a href="https://gohugo.io/" target="_blank" rel="noopener noreffer" title="Hugo 0.86.0">Hugo</a> 强力驱动 | 主题 - <a href="https://github.com/khusika/FeelIt" target="_blank" rel="noopener noreffer" title="FeelIt 1.0.1"><i class="fas fa-hand-holding-heart fa-fw"></i> FeelIt</a>
        </div><div class="footer-line" itemscope itemtype="http://schema.org/CreativeWork"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2023</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="/"></a></span></div>
</div>
</footer>
        </div>

        <div id="fixed-buttons"><a href="#" id="back-to-top" class="fixed-button" title="回到顶部">
                <i class="fas fa-chevron-up fa-fw"></i>
            </a></div><link rel="stylesheet" href="/lib/fontawesome-free/all.min.css"><link rel="stylesheet" href="/lib/animate/animate.min.css"><link rel="stylesheet" href="/lib/katex/katex.min.css"><link rel="stylesheet" href="/lib/katex/copy-tex.min.css"><script src="/lib/autocomplete/autocomplete.min.js"></script><script src="/lib/lunr/lunr.min.js"></script><script src="/lib/lunr/lunr.stemmer.support.min.js"></script><script src="/lib/lunr/lunr.zh.min.js"></script><script src="/lib/lazysizes/lazysizes.min.js"></script><script src="/lib/clipboard/clipboard.min.js"></script><script src="/lib/sharer/sharer.min.js"></script><script src="/lib/katex/katex.min.js"></script><script src="/lib/katex/auto-render.min.js"></script><script src="/lib/katex/copy-tex.min.js"></script><script src="/lib/katex/mhchem.min.js"></script><script>window.config={"code":{"copyTitle":"复制到剪贴板","maxShownLines":200},"comment":{},"math":{"delimiters":[{"display":true,"left":"$$","right":"$$"},{"display":true,"left":"\\[","right":"\\]"},{"display":false,"left":"$","right":"$"},{"display":false,"left":"\\(","right":"\\)"}],"strict":false},"search":{"highlightTag":"em","lunrIndexURL":"/index.json","lunrLanguageCode":"zh","lunrSegmentitURL":"/lib/lunr/lunr.segmentit.js","maxResultLength":100,"noResultsFound":"没有找到结果","snippetLength":50,"type":"lunr"}};</script><script src="/js/theme.min.js"></script></body></html>
